package edu.cmu.cs211.pg.algorithms;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeMap;

/**
 * 
 */
public class UnionFind<T> 
{	
	private HashMap<T, Node<T>> uf;
	
	public UnionFind() 
	{
		uf=new HashMap<T, Node<T>>();
	}
	
	/**
     * Unions the sets containing elements a and b together. If a and b
     * are already in the same set, this method will do nothing.
     *
     * @throws NullPointerException if a or b is null
     */
	
	/*
	 * this method calls find which calls a helperfind() method which is used
	 * recursively.
	 * Find puts the nodes together into the same set if the sets are disjoint
	 * if they are in the same set, it does nothing
	 */
	public void union(T a, T b)
	{
		if(a.equals(null) || b.equals(null))
			throw new NullPointerException();
		T rootA=find(a);
		T rootB=find(b);
		if(uf.get(rootA).rank>uf.get(rootB).rank){
			uf.get(rootB).parent=rootA;
		}
		else if(uf.get(rootA).rank<uf.get(rootB).rank){
			uf.get(rootA).parent=rootB;
		}
		else{
			uf.get(rootB).parent=rootA;
			uf.get(rootA).rank=uf.get(rootA).rank+1;
		}
	}
	
	/**
     * Returns the canonical element representing the set a is in.
     * 
     * @param a     the element to be queried
     * @return      the canonical element representing the set a is in
     * @throws      NullPointerException if a is null
	 */
	/*
	 * finds the set that a is in and returns a representation of it
	 */
	public T find(T a) 
	{
		if(a.equals(null))
			throw new NullPointerException();
		
		if(!uf.containsKey(a)){
			uf.put(a, new Node<T>(a, a)); //a is in its own set

			return a;
		}
		
		T temp=findHelper(uf.get(a));
		
		return temp;
	}
    private T findHelper(Node<T> node){
    	if(node.equals(null))
    		throw new NullPointerException();
    	
		if(node.parent==node.val)	
    		return node.val;
		
		else{
			node.parent=findHelper(uf.get(node.parent));
			uf.put(node.val, node);
			return node.parent;
		}	  
    }
	/**
	 * Resets this Union-Find so that each element is its own canonical element (ie.
     * each element is in its own set).
     */
	public void clear() 
	{
		Iterator<T> itr=uf.keySet().iterator();
		while(itr.hasNext()){
			T temp=itr.next();
			uf.put(temp, new Node<T>(temp, temp));  //not 100% sure this is right
		}
	}
	
	/*
	 * node class in order to store some information about passed in values
	 */
	private static class Node<T>{
		public final T val;
		public T parent;
		public int rank;
		
		public Node(T val, T parent){
			this.val=val;
			this.parent=parent;
			rank=0;
		}
		
		public T getVal(){
			return val;
		}
		
		public T parentVal(){
			return parent;
		}
		
		public int getRank(){
			return rank;
		}
		public boolean equals(Node<T> a){
			return this.val.equals(a);
		}
	}
}
